package cn.qyd.sort;

import java.util.Arrays;

/**
 * @author 邱运铎
 * @date 2024-03-26 1:56
 */
public class QuickSort02 {
    public static void main(String[] args) {
//        int[] data = new int[]{9,-36,30,23,-30,-49,25,21,30};
        int[] data = new int[]{4,2,1,4,5,6,4};
//        int[] data = new int[]{1,2};
        System.out.println("输出排序之前的数组:\n" + Arrays.toString(data));
        quickSort(data);
        System.out.println("排序之后的数组：\n"+Arrays.toString(data));
    }
    private static void swap(int[] data ,int i,int j) {
        int temp = data[i];
        data[i] = data[j];
        data[j] = temp;
    }

    /*
     * 快排的核心方法------递归的部分
     */
    private static void subSort(int[] data,int start,int end) {
        if(start < end ) {
            int base = data[start];
            int low = start;
            int high = end+1;
            while(true) {
                while(low < end && data[++low] - base <= 0);
                while(high > start && data[--high] - base >= 0);
                if(low < high) {
                    swap (data,low,high);
                }else {
                    break;
                }
            }
            swap(data,start,high);
            subSort(data,start,high-1);
            subSort(data,high+1,end);
        }
    }

    public static void quickSort(int[] data) {
        subSort(data,0,data.length-1);
    }
}
